package 剑指offer;

public class p68_I二叉搜索树的最近公共祖先 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //结合 二叉搜索树BST的特点：左子树节点值 < 根节点值  >  右子树节点值
        if(root==null) {
            return null;
        }

        //p q 小于根节点，则最近公共祖先在左子树中
        if (root.val>p.val && root.val>q.val) {
            return lowestCommonAncestor(root.left,p,q);
        }
        //p q 大于根节点，则最近公共祖先在右子树中
        if (root.val<p.val && root.val<q.val) {
            return lowestCommonAncestor(root.right,p,q);
        }

        //当 p q 一个大于根节点，一个小于根节点，那么最近公共祖先就是当前根节点
        //或者 p q中有一个节点值等于当前根节点的值，那么最近公共祖先也是当前根节点
        return root;
    }
}
